package com.cet.qz.unit01.chapter1_3;

/**
 * @program: algorithm
 * @description: 移除链表中所有item域为key的节点
 * @author: 陈恩涛
 * @create: 2021-04-15 21:40
 **/
public class Qz1_3_26 {

    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }


    public static Node remove(Node first, String key) {
        if (first == null) {
            return first;
        }
        if (first.next == null && key.equals(first.item)) {
            first = null;
            return first;
        }

        Node current = first;

        while (current.next != null) {
            //当前节点为头结点
            if (first == current && key.equals(current.item)) {
                //注意，这里仅仅改变了参数first指向堆内存的地址
                first = first.next;
                current = current.next;
            } else if (key.equals(current.next.item)) {
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        return first;
    }

    private static void printLink(Node node) {
        Node tmp = node;
        while (tmp != null) {
            System.out.println(tmp.item);
            tmp = tmp.next;
        }
    }

    public static void main(String[] args) {
        Node<String> first = new Node<>();
        first.item = "tmp";
        Node<String> second = new Node<>();
        second.item = "second";
        Node<String> third = new Node<>();
        third.item = "third";

        Node<String> tmp1 = new Node<>();
        tmp1.item = "tmp";

        Node<String> tmp2 = new Node<>();
        tmp2.item = "tmp";

        Node<String> fourth = new Node<>();
        fourth.item = "fourth";

        first.next = second;
        second.next = third;
        third.next = tmp1;
        tmp1.next = tmp2;
        tmp2.next = fourth;

        Node result = remove(first, "tmp");
        printLink(result);
    }
}
